%File: formatting-instruction.tex
\documentclass[letterpaper]{article}
\usepackage{aaai}
\usepackage{times}
\usepackage{helvet}
\usepackage{courier}
% TODO je to OK? jsou univerzalni?
\usepackage{amssymb}

\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{mdwlist}
\usepackage{paralist}

\frenchspacing
\pdfinfo{
/Title (REMOVED-GAME-TITLE: Planning Used in a Level Design and During a Gameplay)

/Subject (Planning)
/Author (NA)}
\setcounter{secnumdepth}{0}  
 \begin{document}
% The file aaai.sty is the style file for AAAI Press 
% proceedings, working notes, and technical reports.
%
\title{REMOVED-GAME-TITLE: Planning Used In A Level Design And During A Gameplay}
%\author{AAAI Press\\
%Association for the Advancement of Artificial Intelligence\\
%445 Burgess Drive\\
%Menlo Park, California 94025\\
%}
\maketitle
\begin{abstract}
\begin{quote}

We present a computer game prototype that uses planning as a 
fundamental concept both for level design and also during gameplay. 
A player's goal is to help a computer controlled agent in 
achieving his goal --- stealing an artifact from a museum. The level is partly generated procedurally with the help of a planner and the agent 
is controlled by a planning algorithm. However, the design process 
guarantees the occurrence of pitfalls in the agent's plan that lead to arresting the agent. The player's task is first to identify these pitfalls during the plan execution, 
and then perform sequences of actions changing the environment to force the agent to replan and thus avoid the pitfalls. 

\end{quote}
\end{abstract}


\section{Introduction}

%Our game uses planning in both level design and gameplay.

Even though planning technologies have attracted a lot of attention in academic community dealing with game research, their use in the gaming industry remains limited. % e.g. Interactive Storytelling 
So far, the research has focused mainly on adapting planning techniques for needs of current game genres, be it in design time or during gameplay. However the game industry still prefers traditional approaches of scripting or reactive planning. Even though these techniques are labor intensive, they were verified by years of practice and the industry is used to them.
Besides trying to fit planning in the frame of current games, we can attempt to create brand new types of games that would demonstrate usefulness of planning. 
%That is instead of trying to use planning for decreasing designers burden to create games that would bring the same players experience as the current games we could create games that would bring new experience. Where the planning will be the core technology enabling this experience. 

Interactive Storytelling (IS) may be considered as an attempt in this direction. In IS, the planning is often used as a technology that enables creating or maintaining a coherent story plot. However, the planning is used as an underling technology, the existence of a plan remains hidden to the user. Contrary to this approach we propose new types of games where the fact that we have a complete plan of an agent's actions plays a central role. We can call them \textit{anticipation games}. Imagine you play a game where the main agent has a mission that he must accomplish. He creates a plan for this mission but due to incomplete knowledge of the environment there will be some pitfalls in his plan. The human player has more complete knowledge of the environment, thus when observing execution of the agent's plan, he can  anticipate these pitfalls. Once he identifies a pitfall, he can modify the environment so that the agent has to replan and the new plan avoids this pitfall. The player influences the agent only indirectly through changes of the environment.

 
%   In our example prototype the main agent is controlled by the planning algorithm and player's task is to modify agent's plan, which can be done only indirectly by modification of the game environment, so he successfully achieves the given goal. E.g. a limited number of planned agent's actions can be visualized to the player and he has to anticipate what is the agent going to do next.

%%We adopted this approach and created a game whose core idea is that human player tries to anticipate future actions of the main agent of the game that is controlled by the planner. This idea is enabled by the fact that we have complete plan of agent's actions.

Besides using planning as the key element of the gameplay, we also use it to assist the game designers.

The goal of this paper is to define the genre of anticipation games, present our implemented prototype of one such game and describe algorithms used in its design and gameplay.

The rest of the paper continues as follows. In the next section we detail previous work related to use of planning in games. Then we describe mechanics of our game. Next sections define the problem and show how we use planning in design time and during the game. We close the paper with future work and conclusion.
%TODO zkontrolovat ze odpovida finalni verzi 

\section{Related Work: Planning in Games}

Considering planning in context of computer games, a huge body of work focuses on the use of planners in design and verification of levels, e.g.~\cite{pizzi2008automatic,li2010offline,porteous2009controlling,porteous2011visual}. We consider this an off-line use of planners. %TODO check porteous

On-line use of planning during actual playing a game is limited because of real-time requirements. With respect to commercial games, the most successful algorithm is the GOAP~\cite{orkin2003applying,orkin2006three}, a simplified STRIPS~\cite{fikes1972strips} like planner. So far 14 game titles have used this planner\footnote{For list of commercial games using GOAP see http://web.media.mit.edu/$\sim$jorkin/goap.html, 23.11.2011}. HTN planning is another technique that has been tested for the use in game environments~\cite{hoang2005hierarchica}.%l,munoz2006coordinating}.
Whereas GOAP was created specially for purposes of games, there were also attempts to use off-the-shelf PDDL planners directly in games~\cite{bartheye2009real,bartheye2008connecting}. In accord with IPC challenges there have been recently proposed benchmark tasks motivated by needs of First Person Shooter games~\cite{vassos2011simplefps}.

%\cite{pizzi2008automatic} uses planning to aid level design. Designer can use planning to explore space of level solutions, if he finds some unsatisfactory solutions, he can manually change the initial level setup to fix this problem and again use planner to find all satisfying plans. 

The main difference of our game prototype compared to the above-mentioned systems is that: 1) we use planning in both design time and gameplay, 2) we make existence of the plan key part of the gameplay.

A different body of work related to our game comes from the IS field. We will return to these works when discussing future work.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Game Description}
In this section, we describe a player's perspective of our game's prototype gameplay.
The basic situation in all game levels is that a \textit{burglar} - a computer controlled agent - tries to steal a valuable artifact from a museum secured by an unspecified number of \textit{guards} and \textit{cameras}, which, if turned on, detect the burglar. The complication is that the burglar knows only some of these dangers. The levels are designed in a way that without the help of the player the burglar will be surely caught. The burglar is caught if he gets into the same room with a guard or with an active camera. In the rest of the paper such places will be called \textit{trap rooms}. The only agents in the level are the guards and the burglar.

The human \textit{player} observers the game world from a bird's eye view. The player's role is to change small details of the environment to prevent the burglar getting caught on his mission.
The player wins when the burglar manages to run away with the artifact, he looses if the burglar gets caught.

The game world consists of interconnected \textit{rooms} of different sizes and shapes. 
The rooms can contain one of these objects: \textit{cameras}; \textit{containers}, that can hold \textit{keys}; \textit{artifact}, that is the target for the burglar; \textit{vending machines}, that distract the agents for a while; and finally \textit{doors} between rooms. If a burglar or a guard has a proper key, he can lock a door or a container to prevent their usage by other agents. The player has no such limitation on any object; however, each interaction costs him a price in action points expense of which he should keep minimal. The player can also spend action points to take a look at the visualized plans of agents' future actions, the more actions he sees the more he pays. 

%There are two types of agents on each level, a single \textit{burglar} and an unspecified number of \textit{guards}.
At the beginning of the game the burglar is always placed at the entrance of the game area, and that is also the place where he has to return at the end. 
%In between he must reach the artifact hidden somewhere in the museum. 
At the beginning the burglar knows the layout of the map, exact position of the artifact and possibly positions of some traps. Based on this incomplete knowledge, the agent makes a plan how to steal the artifact and then escape from the museum. However it is guaranteed by the design process that his plan will contain pitfalls. There will always be trap rooms on his way and it is the player's task to make the burglar avoid them.
For instance, there are guards patrolling predefined rooms. As soon as the player finds out that they would probably meet the burglar in the same room he/she must change state of the environment so they miss each other.

The burglar and every guard has its own belief base about the environment, that they use to plan future actions. Theirs knowledge may of course be wrong.
The belief-base is updated whenever the agent finds an inconsistency with the world state. This triggers replanning and thus it may cause change of the actual plan. Through the game, it is up to the player to predict the actions of the agents. However if he/she decides to spend action points to take a look at the visualized plan of a selected individual, the view also highlights where the belief base of the agent differs from the real world state.

On Figure \ref{fig:gameScreenshot34} there are two game situations. On the left image, the player is locking a door on the burglar's path to prevent him encounter the guard. When the burglar discovers that the doors are closed, he chooses another path. The right image captures this situation, and also points out that there is another locked door on the agent's new path, that he is not yet aware of. 

%A single game level consists of the above described objects - a layout, objects and agents, their positioning and exact state that includes theirs' belief bases. These levels are partially generated by our level design application, while the actual agent behaviour is created through the gameplay itself.
The difficulty of a level is given by the number of places where the player has to assist the burglar. The harder the level, the more trap rooms are put to the world, but on the other hand there has to be some sequence of actions (including the player's actions) leading to a successful end.

\begin{figure}[ht]
	\centerline{\includegraphics[width=1\columnwidth]{media/screenshot_34_numbered.png}}
	\caption{
		Locking a door causes the choice of another path, seen from the burglar's perspective.
		Visible objects are:
           	\begin{inparaenum}[\itshape 1\upshape)]
			\item {the \textit{burglar},}
			\item {a \textit{guard},}
			\item {a closed \textit{container},}
			\item {a closed \textit{door}, marked with a darker colour to symbolize it is not fully consistent with the burglar's belief base,}
			\item {the level \textit{entrance},}
			\item {a \textit{camera}, that is marked with deep dark colour to symbolize that it is completely unknown to the burglar,}
			\item {an \textit{intent line} showing the future path of the burglar in the game area with arrows to mark his direction,}
			\item {a \textit{container} holding the \textit{artifact}, with textual description what the burglar intents to do with it.}
		\end{inparaenum}
	}
	\label{fig:gameScreenshot34}
\end{figure}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Problem Definition}

In order to formally define the planning problem solved in our game we will use following notation: 
$M=\langle Rooms, Doors \rangle$ is a planar graph representing map of the level, a state of each door is given by a function
$
Ds: Doors \to \{locked, unlocked\}
$;
$O$ is a set of operable objects, each object $o \in O$ can also have its internal state given by function $Os: O \to propositions\ about\ objects$ (e.g. container can be \textit{closed} or \textit{opened});
$G$ is a set of guards patrolling the level;
$b$ is the single burglar;
$E = O \cup G \cup \{b\}$ stands for a set of all entities in the level;
function $EtoR: E \to Rooms$ assigns each entity to one room;
$A$ stands for a set of possible instantiated player's actions.

%   each agent is specified by its starting position, planning goal and knowledge of objects' states, we call this agent's \textit{belief base}; 

Now we can define a world state of map $M$ as $S^M = \langle E, Os, EtoR, Ds \rangle \in \mathcal{S^M}$, where $\mathcal{S^M}$ denotes a set of all possible world states on the given map $M$.
$S^M_{burglar} \in \mathcal{S^M}$ denotes a state of the world believed to be true by the burglar, $S^M_{real} \in \mathcal{S^M}$ denotes a real state of the world perceivable by the human player. Game level $L$ is defined by a triplet $\langle M, S^M_{real}, S^M_{burglar} \rangle$. Predicate $flawed(P,S^M)$ is true if execution of a plan $P$ in a state of the world $S^M$ leads to a situation when the burglar is \textit{caught}. From now on we omit the upper index in $S^M$ since we take $M$ as fixed.
%   $n \in N$ is a required number of minimal player's changes of the world and $a \in

%To capture the effect of the player's actions on the burglars knowledge, we define an auxiliary function 
%$
%H(a, P, S_{burglar}) = S'_{burglar}
%$.
%It models a situation where the player executes an action $a \in A$ and due to the effects of $a$ the burglar can no longer follow its current plan $P$, hence he stops and updates its world state $S_{burglar}$ with previously unknown effects of $a$, which results in the new state $S'_{burglar}$.

To capture the effect of the player's actions on the burglars knowledge, we define an auxiliary function 
$
H(\bar{A}, S_{burglar}) = S'_{burglar}
$.
It models a situation where the player executes actions $\bar{A} \subseteq A$ and due to theirs effect burglar updates his belief to the new state $S'_{burglar}$.

Now we can define the problem that has to be solved in a design time as finding at least some solutions of function 
%$F: \mathcal{L} \times N \to 2^{\mathcal{S} \times \mathcal{S}}$
$F: \mathcal{S} \times \mathbb{N} \to 2^{\mathcal{S}}$. $F$ gets an initial world state $S_{init}$ and a number of pitfalls $n$ and outputs the set of world states that can be known to the burglar at the beginning of the game.
We will now discuss several possible definitions of function $F$. The first version of the definition that is implemented by our prototype is:
%\begin{gather}
% \forall \langle S_{burglar}, S_{real}\rangle \in F(L,n) \nonumber \\
%  \iff \nonumber \\
% \exists P:\neg flawed(P, S_{burglar}) \wedge flawed(P, S_{real}) \wedge \label{eq:believable} \\ 
%  \wedge \nonumber \\
%\exists a \in A: H(a, P, S_{burglar}) = S'_{burglar} \wedge \label{eq:userAct} \\
% \wedge \nonumber \\
%\langle S'_{burglar}, S_{real} \rangle \in F(L, n-1) \wedge \label{eq:recursive} \\
% \wedge \nonumber \\
%\forall k < n - 1 : \langle S'_{burglar}, S_{real} \rangle \notin F(L, k) \label{eq:minimal}
%\end{gather}
\begin{gather}
 S_{burglar} \in F(S_{real},n)  \equiv \nonumber \\
%  \exists T: T(S_{init}) = S_{real}  \wedge \\
 \exists P:\neg flawed(P, S_{burglar}) \wedge flawed(P, S_{real})~\wedge \label{eq:believable} \\ 
%  \wedge \nonumber \\
\exists \bar{A}  \subseteq A: H(\bar{A}, S_{burglar}) = S'_{burglar}~\wedge \label{eq:userAct} \\
% \wedge \nonumber \\
|trapRoomsPresentInPlan(P)|=n~\wedge \label{eq:trapRooms} \\
\exists P': \neg flawed(P', S'_{burglar}) \wedge \neg flawed(P', S_{real}) \label{eq:ok}
% S'_{burglar} \in F(L, n-1) \wedge \label{eq:recursive} \\
% \wedge \nonumber \\
%\forall k < n - 1 : \langle S'_{burglar}, S_{real} \rangle \notin F(L, k) \label{eq:minimal}
\end{gather}

We require that there is a plan that seems to be solving the task given the burglar's initial knowledge but it contains pitfalls in reality (Cond.~\ref{eq:believable}), further there must be the user's actions that make the burglar change its belief base to the new state $S'_{burglar}$ (Cond.~\ref{eq:userAct}), the number of trap rooms in the plan must be $n$ (Cond.~\ref{eq:trapRooms}) and there must be the new plan $P'$ that is without trap rooms both in $S'_{burglar}$ and $S_{real}$ (Cond.~\ref{eq:ok}).

This definition can lead to creating levels where the initial burglar's plan contains $n$ pitfalls but it can be solved with just one user's action. There is the plan $P'$  that is solving correctly the problem in $S'_{burglar}$.

We could also propose an alternative, more restricted, definition of $F'$.
First we define an alternative to $H$.
$
H'(a, P, S_{burglar}) = S'_{burglar}
$ 
models a situation where the player executes an action $a \in A$ and due to the effects of $a$ the burglar can no longer follow its current plan $P$, hence he stops and updates its world state with previously unknown effects of $a$, which results in the new state $S'_{burglar}$.

 Let for $n \in  \mathbb{N}, n \ge 1$ $F'$ fulfils the following condition:
\begin{gather}
S_{burglar}\in F'(S_{real}, n) \equiv (\ref{eq:believable})~\wedge \nonumber \\ 
\exists a  \in A: H'(a, P, S_{burglar}) = S'_{burglar}~\wedge \label{eq:userAct2} \\
S'_{burglar} \in F'(S_{real}, n-1)~\wedge \label{eq:recursive} \\
\forall k < n - 1 :  S'_{burglar} \notin F'(S_{real}, k)~\label{eq:minimal}
\end{gather}

For $n = 0$ we define $F'$ as: 
\begin{gather}
S_{burglar} \in F'(S_{real}, 0) \iff  \nonumber \\ 
\exists P: \neg flawed(P, S_{burglar}) \wedge \neg flawed(P, S_{real}) \label{eq:ok2}
\end{gather}

This definition shares the Cond. \ref{eq:believable} with definition of $F$. Then it requires that there is single user's action that makes the burglar stop and update its world state to $S'_{burglar}$ (Cond. \ref{eq:userAct2}); given $S'_{burglar}$, the burglar can choose a plan with $n - 1$ pitfalls (Cond.~\ref{eq:recursive}) but not less (Cond.~\ref{eq:minimal}). When the recursion reaches its end we require that the burglar can choose a plan that is solving the goal not only in his belief base but also in the real state of the world (Cond.~\ref{eq:ok2}).

If we compare $F$ and $F'$, $F$ requires the player to make at least one action, whereas $F'$ requires full sequence of $n$ player's actions. On the other hand $F$, is easier to compute. We want to implement $F'$ in future versions but currently we use the definition $F$.

%\begin{gather}
%\forall S_{burglar} \in G(S_{real},n) \iff \nonumber (\ref{eq:believable}) \wedge (\ref{eq:userAct}) \wedge \\
%S'_{burglar} \in G(L, n-1) \wedge \label{eq:recursive} 
%\end{gather}
In the next section, we specify how we implement our level design algorithm according to definition $F$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Level Design}

%In this section we describe When finding solutions of function $F$ 
%As was said above, level design tries to find at least some solution of  

In our design process, the designer specifies the initial state of the world $S_{init}$ and number of pitfalls $n \in \mathbb{N}$. $S_{init}$ contains a fully specified map of the level $M$. $M$ remains fixed in the design process; however, the set of entities $E$ and theirs assignment to rooms $EtoR$ and doors' resp. objects' states ($Ds$ resp. $Os$) can be modified. The burglar does not have to know about all these objects and guards. The output of the design process is the real state of the world observable by the player, $S_{real}$, the state known to the burglar, $S_{burglar}$, and a number of successfully assigned pitfalls $k \leq n$. $k$ is less than $n$ if the algorithm fails to add all the required pitfalls.

%The key to our automated level design is to correctly select the trap rooms. If accomplished, the exact trap types can be selected easily. The rest of this section will describe the way we accomplish the room selection, and a simplified process is demonstrated in Algorithm~\ref{levelDesign}.

%The designer can specify the number of trap rooms that is required to occur on burglar's path during execution of his plan. On the other hand the plan must leave the player some way of solving all problems. 
%For this reason every layout has a maximal number of dangers that it can accommodate. %The designing algorithm has to calculate this number and not allow putting there any more.

%The input is an XML file containing the layout, the burglar with his belief base, artifact's location and other objects required by the human level designer.
%The output of the process is a modified map file containing the extra information added by our program about object states, generated alarms and guards.

Our design algorithm (see Algorithm~\ref{levelDesign}) uses the planner to determine the expected plan $P$ of the burglar in $S_{init}$. In the next step, it filters out the rooms that the burglar is unable to avoid, like graph chokepoints, or rooms that hold objects necessary for completion of burglar's mission. Then it tries to remove all subsets of rooms present in plan $P$ and ask the planner to generate a new plan. If the planner finds a new solution then we can put pitfalls like cameras or guards into these previously removed rooms. 

%The rest of the rooms in P are organized into random combinations the size of the required number of traps and each combination is tested whether it produces a solvable level.

\algsetup{indent=2em}
%\newcommand{\factorial}{\ensuremath{\mbox{\sc Evolution}}}
\begin{algorithm}
\caption{Level design}
\label{levelDesign}
\begin{algorithmic}[1]

\REQUIRE $S_{init}$ --- initial world state by the designer
\REQUIRE $n$ --- number of required pitfalls in the level
\ENSURE trap rooms are assigned to the world state

\STATE $P \leftarrow$ createPlan($S_{init}$)
\STATE $rooms \leftarrow$ allRoomsIn($P$) $\setminus$ unavoidableRoomsIn($P$)  

\FOR{$k=n$ \TO 1 }		
	\FORALL{$trapRooms \subseteq rooms \wedge |trapRooms| = k$}
		%\STATE $P' \leftarrow$ createPlan($S_{trapped}$)
		\STATE $S_{reduced} \leftarrow S_{init}$ without $trapRooms$ in layout 
		%\STATE $P'' \leftarrow$ createPlan($S_{reduced}$)
		\IF{$\exists P': P' =$ createPlan($S_{reduced}$)}
			\STATE $S_{real} \leftarrow S_{init}$ with traps in $trapRooms$ 
			\STATE $S_{burglar} \leftarrow S_{init}$ without traps in $trapRooms$ 
			\RETURN $\langle S_{real}, S_{burglar}, k \rangle$
		\ENDIF
	\ENDFOR

\ENDFOR

\RETURN $null$


%muj alternativni popis

%\STATE $rooms \leftarrow$ allRooms($S_{init}$) $\setminus$ unavoidableRooms($S_{init}$)  

%\FOR{$k=n$ \TO 1 }		
%	\FORALL{$trapRooms \subseteq rooms \wedge |trapRooms| = k$}
%		\STATE $S_{real} \leftarrow S_{init}$ with traps put to $trapRooms$ 
%		
%		\STATE $P \leftarrow$ createPlan($S_{real}$)
%		\IF{$\neg flawed(P, S_{trapped}) \wedge flawed(P, S_{real})$}
%			\RETURN $\langle S_{trapped}, S_{init} \rangle$
%		\ENDIF
%	\ENDFOR

%\ENDFOR

%\RETURN $null$

\end{algorithmic}
\end{algorithm}

The reason why such a design method works is based on the deterministic behavior of the used planner. After diverting from his original plan and thus avoiding a single trap, the agent will try to return to his original path. This of course presumes that the planner used at the design time is the same as the one used through out the gameplay itself.

Note that the present algorithm has exponential time complexity, however it is run only in the design time.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\section{Gameplay}

%In the game itself the player selects a generated level, and starts observing it. The burglar and guards use the external planner to devise their plans upon their beliefs and start executing them. After the player has found out what the agents are up to, he makes changes in the level to save the burglar. % and let the gameworld execute it's plans.

%The agents' perceptions work in two modes. In first mode they can look around a room and notice existence of all present objects, but not their exact details (i.e. whether the doors are only closed or locked). The second, more detailed, mode of perceiving is limited only to an object they try to operate and it shows exact state of all properties of the object (i.e. the agent founds that the doors were closed when he tried to open them). 

%There are two approaches to the replanning. In the first the agents replan every time they come upon a new piece of information, or find any inconsistency in their belief base. This makes their movement more believable, but also makes their final path of action highly unpredictable for the level design process. Trying to predict, or simulating future knowledge changes drastically increases the time required to create a new level.We tested this approach and decided to implement another, more computationally effective.

%In the second approach, used in the current version, the agents only reconsider their plans if they come upon an instruction they are unable to execute (i.e. they find a locked object without key to it, or simply on a door that should have been open according to their beliefs).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Gameplay: Agent Planning Details}

In the on-line phase the burglar and guards can perform the following actions: \textit{approach, open, close, lock, unlock, enter} and \textit{operate}. All these actions are atomic and take exactly one time unit to execute. Actions related to game objects can be performed only when the agent stands right next to the object. From the planner's point of view there is no difference between room sizes, or distances between objects.

All the agents have a single unified planning domain. The only real difference between the two types of agents is in their goals. The guards' goals consist of a list of rooms that they need to visit, while the burglar has a single goal room and an artifact to gather. %TODO Once the guard visits all the rooms he starts again

An agent's decision making procedure simply follows actions of the computed plan and checks whether it should replan. The method used to decide whether the agent has to replan is described in Algorithm~\ref{agentDMS}.

\begin{algorithm}
\caption{One step of an agent's decision making}
\label{agentDMS}
\begin{algorithmic}[1]

\REQUIRE $P$ --- plan that is being executed
\REQUIRE $S_{agent}$ --- agent's prior knowledge of the level
%\REQUIRE $doExplore$ --- whether the agent has to actively look for new routes
%\REQUIRE $room$ --- observed state of the room
%\REQUIRE $o$ --- object that the agent is up to interact with
\ENSURE the agent replans, if necessary

%\STATE $flawedBelief \leftarrow$ checkBeliefs($S_{agent}$, $room$)

%\IF{$doExplore$ \AND $flawedBelief$}
%	\STATE replan()
%\ENDIF

\STATE $actionResult \leftarrow$ executeNextActionFromPlan($P$)

\IF {$actionResult$ == failed}
	\STATE $S_{agent} \leftarrow$ updateBelief($S_{agent}$) 
	\STATE $P \leftarrow$ replan($S_{agent}$)
\ENDIF

\end{algorithmic}
\end{algorithm}

In Algorithm~\ref{agentDMS}, the agent only reconsiders his plan if he comes upon an instruction he is unable to execute (i.e. he finds a locked container that was supposed to be open, without the key to open it).

An alternative approach would be to replan each time the agent finds an inconsistency of his internal believed world state with the real world state. However this can cause much higher frequency of replanning, thus leading to less predictable behavior. We tested this approach but finally we decided to use the first method where the agent replans only when the inconsistency causes a failure of his plan.

Note that generating solutions for the agents and the level building is more complex than path finding. It is not enough to find the shortest route, the acting agents may have to pick up items, use objects, lock and unlock doors; while doing this, the agents change the world state. To control whether there exists a valid solution for a level, the program has to take into account both the agents' and the player's possible actions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Implementation}
The game has been implemented is a Java application, it uses an external game engine Slick~\cite{website:slickengine}, A$^*$ navigation library~\cite{website:astarlibrary} and an external planner, which in the current version is SGPlan \cite{chen2006sgplan}. 
SGPlan can be replaced with other planners capable of solving problems in PDDL 2.2 with a few modifications of the whole program itself. In fact, there is already an interface that can work with several different planners. 

The game prototype is open-source and it is available for download on its homepage\footnote{Homepage of the game is http://code.google.com/REMOVED}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Domain Size and Performance}

The planning domain of the game agents has 10 predicates and 8 different actions. %19 types, 
The largest smoothly running level so far had 28 rooms.
%610 objects, from which 30 is interactive, 2 items, 2 agents. Adding agents and items to this map was not a priority, extra agents doe not increase the planning problem complexity, they cause only more frequent replanning. 
When translated to the burglar's PDDL planning problem this level had 72 PDDL objects and 175 initial facts. The exact number of facts and objects may vary based on the actual belief base of the agent, but the one used in this example had a near flawless knowledge of the world. The resulted plan for the problem above contained 75 actions. On the current test configuration, the time required to create such a plan is about 300 ms, that also includes the initial construction of the problem description in PDDL from internal representation in Java and the parsing of the resulted instruction list.

The hardest game world on the planner so far was a 10 by 10 room maze with all neighboring rooms interconnected, where the planner failed to produce sufficiently varied plans in a reasonable time window (the time limit for a single replanning was set to 8 seconds). In this map, generating an alternative plan while avoiding several of the initially selected rooms seemed to be a hard task for the planner.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Future Work}
As long as the whole game concept is based on players ability to predict burglars plans, we need the planer not only to produce \textit{some} plans but even better plans that resemble plans of human. Current off-the-shelf planners are not optimized for this type of constraints, but we can get inspiration from the IS field. For instance there are works that try to extend planning algorithms to account for intentions of agents~\cite{riedl2010narrative}, suspense~\cite{cheong2008narrative} or emotions~\cite{aylett2006affectively}. We think that these properties can make the plans more engaging for humans.

Another extension would be to implement algorithm that will find level designs according to the definition of $F'$. This would guarantee more complex player's interaction and thus probably better game experience. 

There can be also enhancements focusing on increasing speed of the planning by incorporating landmarks~\cite{hoffmann2004ordered} or by using domain dependent heuristics. %We could also extend the definition to require existence of bad player's actions that lead to capturing the burglar.

% We see several directions that can extend our current prototype:
%\begin{inparaenum}[\itshape a\upshape)]
%	\item extending the set of possible objects that the player can interact with;
%	\item speeding up the planning process ;
%	\item ensuring that there are also wrong player actions that worsen the burglar's situation;
%\end{inparaenum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Conclusion}

We have presented a working prototype of our game that uses off-the-shelf planer in design and during playing of the game. We defined novel genre of games that we call the anticipation games. These show new type of use of planning in games. Even though current levels of our game are of medium complexity we think that the game concept can be interesting to both academy and game industry.


\pagebreak
\bibliographystyle{aaai}
\bibliography{literature}

\end{document}
